package com.dyz.leetcode;

public class Flatten114 {
    public void flatten(TreeNode root) {
        if(root==null){return;}
        root = helper(root);
    }
    private TreeNode helper(TreeNode root){
        if(root==null){return null;}

        TreeNode l = helper(root.left);
        TreeNode r = helper(root.right);

        if(l==null){
            root.right = r;
        }else{
            root.right = l;
            TreeNode cur = l;
            while (cur.right!=null){
                cur = cur.right;
            }
            cur.right = r;
            root.left = null;
        }
        return root;
    }

    /**
     * 解法2：递归，从下往上，从右向左走
     */
    private TreeNode last = null;
    //递归，从下往上，从右向左走
    public void flatten1(TreeNode root) {
        if(root==null){return;}
        flatten(root.right);
        flatten(root.left);
        root.right = last;
        root.left = null;
        last = root;
    }
}
